The present invention generally relates to computer-implemented techniques for evolving a solution to a particular problem, and more particularly to a technique that is a hybrid of evolution-based processing techniques and simulated annealing techniques.
Many conventional design methodologies are generally based on a structured design approach. That is, high-level requirements are partitioned, perhaps hierarchically, into lower-level requirements. Teams of engineers are assigned to create designs and sub-designs that meet the requirements at the different levels. The structured design methodology is advantageous because it supports building on past experiences in addressing similar types of requirements, thereby promoting the development of an effective design in an efficient manner. However, a drawback to traditional design methods is that the same experiences that promote quickly satisfying a requirement may blind engineers to alternative, and perhaps better, solutions.
Work is presently underway to fundamentally change the way in which designs are created. The new methodology uses principles of natural selection from the biological world to find hardware and/or software designs. The process is often characterised as using xe2x80x9cgenetic algorithmsxe2x80x9d to find a solution. In an example process of evolving a design, a population of designs is first randomly created, tested, and scored based on the suitability to meet the design requirements. Then, based on natural selection principles, certain ones of the designs in the population are selected to xe2x80x9creproduce,xe2x80x9d that is, are used to create new designs for the population. The process of testing, scoring, and reproducing is then repeated until a suitable design has evolved.
At present, evolving circuits is very time consuming. Many hours or even days can be spent evolving a circuit, depending on the desired functionality of the circuit. Proposed solutions to accelerate the process of evolving a circuit include the use of super-computers, massive clusters of networked microcomputers working in parallel, and custom computers. While any or all of these solutions may reduce the time required to evolve a suitable circuit, each is expensive in terms of the required hardware.
A system and method that address the aforementioned problems, as well as other related problems, are therefore desirable.
In various embodiments, method and apparatus are provided for evolving an object using simulated annealing and genetic processing techniques. In each iteration a single object is mutated in proportion to a mutation level, and the mutated object is evaluated relative to the satisfaction of predetermined criteria. With each iteration, the mutation level is reduced if the present solution is better than the best solution thus far achieved. On each iteration, a poorer-performing object is either kept or its mutations are undone for future iterations based on a probabilistic function. As the object approaches a final solution, the probability of keeping and mutating poorer-performing objects is reduced.
It will be appreciated that various other embodiments are set forth in the Detailed Description and Claims that follow.